#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int MaxSubSum(int* nums, int Left, int Right) {
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBorderSum, MaxRightBorderSum;
    int LeftBorderSum, RightBorderSum;
    int Center, i;

    if (Left == Right) {
        return nums[Left];
    }

    Center = (Left + Right) / 2;
    MaxLeftSum = MaxSubSum(nums, Left, Center);
    MaxRightSum = MaxSubSum(nums, Center + 1, Right);

    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for (i = Center; i >= Left; i--) {
        LeftBorderSum += nums[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }

    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for (i = Center + 1; i <= Right; i++) {
        RightBorderSum += nums[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    }

    int PolarMax = (MaxLeftSum > MaxRightSum) ? MaxLeftSum : MaxRightSum;
    int BorderMax = MaxLeftBorderSum + MaxRightBorderSum;
    return (PolarMax > BorderMax) ? PolarMax : BorderMax;
}

int maxSubArray(int* nums, int numsSize) {
    return MaxSubSum(nums, 0, numsSize - 1);
}

int main() {
    int arr[9] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int ret = MaxSubSum(arr, 0, n - 1);
    printf("%d\n", ret);
    return 0;
}